
// 最短编辑距离
pub fn min_distance(s1: &str, s2: &str) -> i32 {
    let mut m = 0 ;
    let mut n =0 ;
    let mut dp = vec![vec![0i32; n+1]; m+1];

    for (i, c) in s1.char_indices() {
        dp[i][0] = i as i32;
        println!("s1: {}:{}", i,c);
        m += 1;
    }

    for (j,c) in s2.char_indices() {
        dp[0][j] = j as i32;
        n += 1;
        println!("s1: {}:{}", j,&c);
    }

    for i in 1..=m {
        for j in 1..=n {
            
            if s1.chars().as_str()[(i-1) ..i] == s2.chars().as_str()[(j-1) ..j] {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = min3(
                    dp[i-1][j] + 1, 
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                );

            }
        }
    }

    for (i,m) in dp.iter().enumerate() {
        for (j, v) in m.iter().enumerate() {
            println!("{}-{} = {}",i,j,v);
        }
    }

    dp[m][n]
}

fn min3(a: i32, b: i32, c: i32) -> i32 {
    a.min(b).min(c)
}

#[cfg(test)]
mod tests {

    use super::*;
    #[test]
    fn it_works() {
        println!("result: {}",min_distance("intention", "execution"));
        // assert_eq!( min_distance("intention", "execution"), 5);

        let s1 = "我是中国人";
        let s2 = "是人";
        println!("result: {}",min_distance(&s1, &s2));
    }
}
